package demo.practice.leetcode_eveyday;

public class P74 {

    public static void main(String[] args) {
        int [][] matrix= new int[][]{
                {1,3,5,7},{10,11,16,20},{23,30,34,60}
        };

        P74 p74= new P74();
        p74.searchMatrix(matrix,3);

    }


    /**
     * 方式一，将矩阵扁平，然后二分法
     * 方式二，先列方向二分，然后横向二分
     *
     * @param matrix
     * @param target
     * @return
     */
    public boolean searchMatrix(int[][] matrix, int target) {

//        int maxHeight= matrix.length;
//
//        int minHeight=0;
//        int mid= minHeight+(maxHeight-minHeight)/2;

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0)//矩阵为空
            return false;


        int with = matrix[0].length;
        int max = matrix.length-1;
        int min = 0;

        while (max >= min) {//当max=min
            int mid = min + (max - min) / 2;
            if (matrix[mid][0] <= target && target <= matrix[mid][with - 1]) {

                int minIner = 0;
                int maxIner = with - 1;

                while (maxIner >= minIner) {
                    int midIner = minIner + (maxIner - minIner) / 2;

                    if (matrix[mid][midIner] == target) {
                        return true;
                    } else if (matrix[mid][midIner] > target) {
                        maxIner = midIner - 1;
                    } else {
                        minIner = midIner + 1;
                    }
                }

                return false;

            } else if (matrix[mid][0] > target) {
                max = mid - 1;
            } else if (target > matrix[mid][with - 1]) {
                min = mid + 1;
            }
        }

        return false;
    }
}
